{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize Product Sum of Two Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minProductSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个数组的最小乘积和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个<strong>长度相等</strong>的数组<code>a</code>和<code>b</code>，它们的<strong>乘积和</strong>为数组中所有的<code>a[i] * b[i]</code>之和，其中<code>0 &lt;= i &lt; a.length</code>。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比如<code>a = [1,2,3,4]</code>，<code>b = [5,2,3,1]</code>时，它们的<strong>乘积和</strong>为<code>1*5 + 2*2 + 3*3 + 4*1 = 22</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>现有两个长度都为<code>n</code>的数组<code>nums1</code>和<code>nums2</code>，你可以以<strong>任意顺序排序</strong><code>nums1</code>，请返回它们的<strong>最小乘积和</strong>。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> nums1 = [5,3,4,2], nums2 = [4,2,2,5]\n",
    "<strong>输出:</strong> 40\n",
    "<strong>解释: </strong>将 num1 重新排列为 [3,5,4,2] 后，可由<b> </b>[3,5,4,2] 和 [4,2,2,5] 得到最小乘积和 3*4 + 5*2 + 4*2 + 2*5 = 40。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> nums1 = [2,1,4,5,7], nums2 = [3,2,4,8,6]\n",
    "<strong>输出:</strong> 65\n",
    "<strong>解释:</strong> 将 num1 重新排列为 [5,7,4,1,2] 后，可由<b> </b>[5,7,4,1,2] 和 [3,2,4,8,6] 得到最小乘积和 5*3 + 7*2 + 4*4 + 1*8 + 2*6 = 65。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-product-sum-of-two-arrays](https://leetcode.cn/problems/minimize-product-sum-of-two-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-product-sum-of-two-arrays](https://leetcode.cn/problems/minimize-product-sum-of-two-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,4,2]\\n[4,2,2,5]', '[2,1,4,5,7]\\n[3,2,4,8,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # max_min_nums1 = sorted(nums1)\n",
    "        # # print(max_min_nums1)\n",
    "\n",
    "        # min_max_nums2 = sorted(nums2)[::-1]\n",
    "        # # print(min_max_nums2)\n",
    "\n",
    "        # res = 0\n",
    "\n",
    "        # for i in range(len(nums1)):\n",
    "        #     res += max_min_nums1[i] * min_max_nums2[i]\n",
    "\n",
    "        # return res\n",
    "\n",
    "        nums1.sort()\n",
    "        # print(nums1)\n",
    "        nums2.sort()\n",
    "        # print(nums2)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums1)):\n",
    "            res += nums1[i] * nums2[-(i+1)]\n",
    "         \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 排序两个数组\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 升序排序 nums1，降序排序 nums2。\n",
    "        nums1.sort()\n",
    "        nums2.sort(reverse=True)\n",
    "        \n",
    "        # 初始化 sum 为 0。\n",
    "        ans = 0\n",
    "        \n",
    "        # 遍历两个有序数组并计算累积乘积和。\n",
    "        for num1, num2 in zip(nums1, nums2):\n",
    "            ans += num1 * num2\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # max_min_nums1 = sorted(nums1)\n",
    "        # # print(max_min_nums1)\n",
    "\n",
    "        # min_max_nums2 = sorted(nums2)[::-1]\n",
    "        # # print(min_max_nums2)\n",
    "\n",
    "        # res = 0\n",
    "\n",
    "        # for i in range(len(nums1)):\n",
    "        #     res += max_min_nums1[i] * min_max_nums2[i]\n",
    "\n",
    "        # return res\n",
    "\n",
    "        nums1.sort()\n",
    "        # print(nums1)\n",
    "        nums2.sort(reverse=True)\n",
    "        # print(nums2)\n",
    "\n",
    "        res = 0\n",
    "        for n1, n2 in zip(nums1, nums2):\n",
    "            res += n1 * n2\n",
    "         \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ##############method 1\n",
    "        # max_min_nums1 = sorted(nums1)\n",
    "        # # print(max_min_nums1)\n",
    "\n",
    "        # min_max_nums2 = sorted(nums2)[::-1]\n",
    "        # # print(min_max_nums2)\n",
    "\n",
    "        # res = 0\n",
    "\n",
    "        # for i in range(len(nums1)):\n",
    "        #     res += max_min_nums1[i] * min_max_nums2[i]\n",
    "\n",
    "        # return res\n",
    "\n",
    "        #################method 2\n",
    "        # nums1.sort()\n",
    "        # # print(nums1)\n",
    "        # nums2.sort(reverse=True)\n",
    "        # # print(nums2)\n",
    "\n",
    "        # res = 0\n",
    "        # for n1, n2 in zip(nums1, nums2):\n",
    "        #     res += n1 * n2\n",
    "         \n",
    "        # return res\n",
    "\n",
    "        ###############method 3\n",
    "        counter1, counter2 = [0] * 101, [0] * 101\n",
    "\n",
    "        for num in nums1:\n",
    "            counter1[num] += 1\n",
    "        for num in nums2:\n",
    "            counter2[num] += 1\n",
    "        \n",
    "        p1, p2 = 1, 100\n",
    "        res = 0\n",
    "\n",
    "        while p1 <= 100 and p2 >=1:\n",
    "            while p1 <= 100 and counter1[p1] == 0:\n",
    "                p1 += 1\n",
    "            while p2 >= 1 and counter2[p2] == 0:\n",
    "                p2 -= 1\n",
    "            if p1 > 100 or p2 < 1:\n",
    "                break\n",
    "            \n",
    "            max_current_pair = min(counter1[p1], counter2[p2])\n",
    "            res += max_current_pair * p1 * p2\n",
    "            counter1[p1] -= max_current_pair\n",
    "            counter2[p2] -= max_current_pair\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # max_min_nums1 = sorted(nums1)\n",
    "        # # print(max_min_nums1)\n",
    "\n",
    "        # min_max_nums2 = sorted(nums2)[::-1]\n",
    "        # # print(min_max_nums2)\n",
    "\n",
    "        # res = 0\n",
    "\n",
    "        # for i in range(len(nums1)):\n",
    "        #     res += max_min_nums1[i] * min_max_nums2[i]\n",
    "\n",
    "        # return res\n",
    "\n",
    "        nums1.sort()\n",
    "        # print(nums1)\n",
    "        nums2.sort()\n",
    "        nums2 = nums2[::-1]\n",
    "        # print(nums2)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums1)):\n",
    "            res += nums1[i] * nums2[i]\n",
    "         \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "      total = 0\n",
    "      nums1.sort()\n",
    "      nums2.sort(reverse=True)\n",
    "      for i in range(len(nums1)):\n",
    "        total += nums1[i]*nums2[i]\n",
    "      return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums1.sort()\n",
    "        nums2.sort(reverse=True)\n",
    "\n",
    "        res = 0\n",
    "        for num1, num2 in zip(nums1, nums2):\n",
    "            res += num1 * num2\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 排序两个数组\n",
    "    def minProductSum1(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 升序排序 nums1，降序排序 nums2。\n",
    "        nums1.sort()\n",
    "        nums2.sort(reverse=True)\n",
    "        \n",
    "        # 初始化 sum 为 0。\n",
    "        ans = 0\n",
    "        \n",
    "        # 遍历两个有序数组并计算累积乘积和。\n",
    "        for num1, num2 in zip(nums1, nums2):\n",
    "            ans += num1 * num2\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 优先队列\n",
    "    def minProductSum2(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 升序排序 nums1。\n",
    "        nums1.sort()\n",
    "\n",
    "        # 将优先队列 pq 初始化为最大堆，并且将 nums2 中的每个元素添加到 pq\n",
    "        pq = [-num for num in nums2]       \n",
    "        heapq.heapify(pq)\n",
    "        \n",
    "        # 在遍历前初始化乘积和为 0\n",
    "        ans = 0\n",
    "\n",
    "        # 在遍历中\n",
    "        for idx in range(len(nums2)):  \n",
    "            # 添加 nums[idx] 的乘积，移除 pq 中剩下的最大元素。\n",
    "            ans += nums1[idx] * (-heapq.heappop(pq))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 计数排序\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 初始化 counter1 和 counter2。\n",
    "        counter1, counter2 = [0] * 101, [0] * 101\n",
    "\n",
    "        # 记录元素在 nums1 和 nums2 中出现的次数。\n",
    "        for num in nums1:\n",
    "            counter1[num] += 1\n",
    "        for num in nums2:\n",
    "            counter2[num] += 1\n",
    "        \n",
    "        # 初始化两个指针 p1 = 1， p2 = 100。\n",
    "        # 分别表示 counter1[1] 和 counter2[100]。\n",
    "        p1, p2 = 1, 100\n",
    "        ans = 0\n",
    "        \n",
    "        # 当两个指针在有效范围内。\n",
    "        while p1 <= 100 and p2 > 0:\n",
    "\n",
    "            # 如果 counter1[p1] == 0，意味着 counter1 中没有等于 p1 的元素。\n",
    "            # 因此我们将 p1 增加 1\n",
    "            while p1 <= 100 and counter1[p1] == 0:\n",
    "                p1 += 1\n",
    "\n",
    "            # 如果 counter2[p2] == 0，意味着 counter2 中没有等于 p2 的元素。\n",
    "            # 因此我们将 p2 增加 1\n",
    "            while p2 > 0 and counter2[p2] == 0:\n",
    "                p2 -= 1\n",
    "\n",
    "            # 如果任何指针超出了边界，我们停止遍历。\n",
    "            if p1 == 101 or p2 == 0:\n",
    "                break\n",
    "\n",
    "            # 否则，我们最多可以构造 min(counter1[p1], counter2[p2]) \n",
    "            # 我们把 nums1 和 nums2 中的对 {p1, p2} 叫做 occ。\n",
    "            # 每个对有乘积 p1 * p2，因此累积的和被增加了\n",
    "            # occ * p1 * p2。更新 counter1[p1] 和 counter2[p2]。\n",
    "            occ = min(counter1[p1], counter2[p2])\n",
    "            ans += occ * p1 * p2\n",
    "            counter1[p1] -= occ\n",
    "            counter2[p2] -= occ\n",
    "        \n",
    "        # 一旦结束循环，返回 ans 作为乘积和。\n",
    "        return ans       \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums1.sort()\n",
    "        nums2.sort(reverse=True)\n",
    "        return sum(nums1[i]*nums2[i] for i in range(len(nums1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums1.sort()\n",
    "        nums2.sort(reverse=True)\n",
    "        ans=0\n",
    "        for i,a in enumerate(nums1):\n",
    "            ans+=a*nums2[i]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        nums1.sort()  # 排序nums1从小到大\n",
    "        nums2.sort(reverse=True)  # 排序nums2从大到小\n",
    "\n",
    "        result = sum(a*b for a, b in zip(nums1, nums2))\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return sum(x * y for x, y in zip(sorted(nums1), sorted(nums2, reverse=True)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return sum(x * y for x, y in zip(sorted(nums1), sorted(nums2, reverse=True)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return sum(x * y for x, y in zip(sorted(nums1), sorted(nums2, reverse=True)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        max_min_nums1 = sorted(nums1)\n",
    "        # print(max_min_nums1)\n",
    "\n",
    "        min_max_nums2 = sorted(nums2)[::-1]\n",
    "        # print(min_max_nums2)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(nums1)):\n",
    "            res += max_min_nums1[i] * min_max_nums2[i]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 排序两个数组\n",
    "    def minProductSum1(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 升序排序 nums1，降序排序 nums2。\n",
    "        nums1.sort()\n",
    "        nums2.sort(reverse=True)\n",
    "        \n",
    "        # 初始化 sum 为 0。\n",
    "        ans = 0\n",
    "        \n",
    "        # 遍历两个有序数组并计算累积乘积和。\n",
    "        for num1, num2 in zip(nums1, nums2):\n",
    "            ans += num1 * num2\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 优先队列\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # 升序排序 nums1。\n",
    "        nums1.sort()\n",
    "\n",
    "        # 将优先队列 pq 初始化为最大堆，并且将 nums2 中的每个元素添加到 pq\n",
    "        pq = [-num for num in nums2]       \n",
    "        heapq.heapify(pq)\n",
    "        \n",
    "        # 在遍历前初始化乘积和为 0\n",
    "        ans = 0\n",
    "\n",
    "        # 在遍历中\n",
    "        for idx in range(len(nums2)):  \n",
    "            # 添加 nums[idx] 的乘积，移除 pq 中剩下的最大元素。\n",
    "            ans += nums1[idx] * (-heapq.heappop(pq))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        a = sorted(nums1)\n",
    "        b = sorted(nums2, reverse=True)\n",
    "        return sum([a[i] * b[i] for i in range(len(a))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return sum([x * y for x, y in zip(sorted(nums1), sorted(nums2, reverse=True))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        return sum([i*j for i,j in zip(sorted(nums1),sorted(nums2,reverse=True))])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
